This invention relates to digital memories; and more particularly, it relates to those digital memories that have error-correcting capability.
In the prior art, a wide variety of digital memories exist. They include dynamic RAMs (DRAMs), static RAMs (SRAMs), electrically programmable read-only memories (EPROMs), and mask programmable read-only memories (ROMs). These memories are described, for example, in a book entitled The MOS Memory Data Book for Design Engineers, Texas Instruments, 1980.
Ideally, all of these memories operate to store digital data bits which are read from the memory as the data is needed. However, all of these memories are also susceptible to errors which cause the data that is read from the memory to be different than the data that was stored (or was intended to be stored) in the memory.
Any one of a wide variety of failure mechanisms may cause these errors. For example, in a dynamic RAM, irradiation in the form of alpha particles can destroy the data bits in one of the memory's cells. As another example, in a mask programmable read-only memory, a minor defect in the mask that programs the memory can cause erroneous data to be permanently written into a cell.
Thus, various structures have been devised in the prior art to detect and correct memory errors. One of these structures involves the encoding of each word of data in a Hamming code and the storing of those encoded words in the memory. Thereafter, when a data word is read, the Hamming code is checked to see if it is a valid code; and if it is not, the bit in error is corrected according to the Hamming error-correction procedure.
However, the Hamming approach is unattractive because it requires the memory's storage capacity to be greatly increased in order to accommodate the data bits plus the code bits. This is evident by inspection of FIG. 1 wherein the leftmost column lists the number of data bits per word; the middle column lists the corresponding number of Hamming check bits per word that are required to detect and correct a single bit error; and the rightmost column lists the corresponding overhead or increase in memory storage capacity.
As the rightmost column shows, this overhead for the commonly used word lengths of eight bits and sixteen bits respectively is 62.5% and 37.5%. This can be verified, for example, by the discussions at page 321 of a book, Digital Computer System Principles, Herbert Hellerman, 1967.
Another mechanism for detecting and correcting memory errors, and which requires less memory overhead than the Hamming code approach, is described in a recent article, "Low Cost Alternative to Hamming Code Corrects Memory Errors", Lee Edwards, Computer Design, July, 1981, pp. 143-148.
There the memory is divided into blocks as illustrated herein as FIG. 2. Each block contains several data words. Associated with each data word in the block is a word parity bit. And associated with all of the data words in a block is one word of vertical parity bits.
Inspection of FIG. 2 shows that the memory overhead which the Edwards mechanism requires is in fact reduced in comparison to the Hamming mechanism. However, the Edwards mechanism presents the new problem of being too slow in its error-correcting procedure.
When a data word is read from an Edwards memory block, the parity bit associated with that word is checked. Then if that check indicates the word is in error, the device which read the word (e.g., a computer) traps to an error routine to sequentially read all of the other words in the block.
This reading of all of the words in the block is a very time-consuming operation. But those words must be read so that the vertical parity word of the block can be recalculated. This recalculated vertical parity word is then compared with the stored vertical parity word to determine which bit in the original fetched data word is in error.
Suppose, for example, that each block had 2,048 words as Edwards suggests in his paper at page 145, and the access time per word of data in one block was 100 nanoseconds. Then, to correct an error would take 2,048 times 100 nanoseconds or 204 microseconds, plus the time needed to recalculate the vertical parity bits.
Of course, the error-correcting time in the Edwards mechanism can be reduced by decreasing the number of words per block. However, as the number of words per block decreases, the ratio of parity bits to data bits per block increases. So in other words, the memory overhead goes up.
Accordingly, it is a primary object of this invention to provide an improved error-correcting memory.
Another object of this invention is to provide an error-correcting memory which requires relatively few check bits and also corrects errors relatively quickly.